home *** CD-ROM | disk | FTP | other *** search
/ Mac Easy 2010 May / Mac Life Ubuntu.iso / casper / filesystem.squashfs / usr / share / guile / 1.8 / ice-9 / q.scm < prev    next >
Encoding:
Text File  |  2008-12-17  |  4.2 KB  |  154 lines
  1. ;;;; q.scm --- Queues
  2. ;;;;
  3. ;;;;     Copyright (C) 1995, 2001, 2004, 2006 Free Software Foundation, Inc.
  4. ;;;;
  5. ;;;; This library is free software; you can redistribute it and/or
  6. ;;;; modify it under the terms of the GNU Lesser General Public
  7. ;;;; License as published by the Free Software Foundation; either
  8. ;;;; version 2.1 of the License, or (at your option) any later version.
  9. ;;;; 
  10. ;;;; This library is distributed in the hope that it will be useful,
  11. ;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. ;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13. ;;;; Lesser General Public License for more details.
  14. ;;;; 
  15. ;;;; You should have received a copy of the GNU Lesser General Public
  16. ;;;; License along with this library; if not, write to the Free Software
  17. ;;;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  18. ;;;;
  19.  
  20. ;;; Commentary:
  21.  
  22. ;;; Q: Based on the interface to
  23. ;;;
  24. ;;; "queue.scm"  Queues/Stacks for Scheme
  25. ;;;  Written by Andrew Wilcox (awilcox@astro.psu.edu) on April 1, 1992.
  26.  
  27. ;;; {Q}
  28. ;;;
  29. ;;; A list is just a bunch of cons pairs that follows some constrains,
  30. ;;; right?  Association lists are the same.  Hash tables are just
  31. ;;; vectors and association lists.  You can print them, read them,
  32. ;;; write them as constants, pun them off as other data structures
  33. ;;; etc. This is good.  This is lisp.  These structures are fast and
  34. ;;; compact and easy to manipulate arbitrarily because of their
  35. ;;; simple, regular structure and non-disjointedness (associations
  36. ;;; being lists and so forth).
  37. ;;;
  38. ;;; So I figured, queues should be the same -- just a "subtype" of cons-pair
  39. ;;; structures in general.
  40. ;;;
  41. ;;; A queue is a cons pair:
  42. ;;;        ( <the-q> . <last-pair> )
  43. ;;;
  44. ;;; <the-q> is a list of things in the q.  New elements go at the end
  45. ;;; of that list.
  46. ;;;
  47. ;;; <last-pair> is #f if the q is empty, and otherwise is the last
  48. ;;; pair of <the-q>.
  49. ;;;
  50. ;;; q's print nicely, but alas, they do not read well because the
  51. ;;; eq?-ness of <last-pair> and (last-pair <the-q>) is lost by read.
  52. ;;;
  53. ;;; All the functions that aren't explicitly defined to return
  54. ;;; something else (a queue element; a boolean value) return the queue
  55. ;;; object itself.
  56.  
  57. ;;; Code:
  58.  
  59. (define-module (ice-9 q)
  60.   :export (sync-q! make-q q? q-empty? q-empty-check q-front q-rear
  61.        q-remove! q-push! enq! q-pop! deq! q-length))
  62.  
  63. ;;; sync-q!
  64. ;;;   The procedure
  65. ;;;
  66. ;;;        (sync-q! q)
  67. ;;;
  68. ;;;   recomputes and resets the <last-pair> component of a queue.
  69. ;;;
  70. (define (sync-q! q)
  71.   (set-cdr! q (if (pair? (car q)) (last-pair (car q))
  72.           #f))
  73.   q)
  74.  
  75. ;;; make-q
  76. ;;;  return a new q.
  77. ;;;
  78. (define (make-q) (cons '() #f))
  79.  
  80. ;;; q? obj
  81. ;;;   Return true if obj is a Q.
  82. ;;;   An object is a queue if it is equal? to '(() . #f)
  83. ;;;   or it is a pair P with (list? (car P))
  84. ;;;                      and (eq? (cdr P) (last-pair (car P))).
  85. ;;;
  86. (define (q? obj)
  87.   (and (pair? obj)
  88.        (if (pair? (car obj))
  89.        (eq? (cdr obj) (last-pair (car obj)))
  90.        (and (null? (car obj))
  91.         (not (cdr obj))))))
  92.  
  93. ;;; q-empty? obj
  94. ;;;
  95. (define (q-empty? obj) (null? (car obj)))
  96.  
  97. ;;; q-empty-check q
  98. ;;;  Throw a q-empty exception if Q is empty.
  99. (define (q-empty-check q) (if (q-empty? q) (throw 'q-empty q)))
  100.  
  101. ;;; q-front q
  102. ;;;  Return the first element of Q.
  103. (define (q-front q) (q-empty-check q) (caar q))
  104.  
  105. ;;; q-rear q
  106. ;;;  Return the last element of Q.
  107. (define (q-rear q) (q-empty-check q) (cadr q))
  108.  
  109. ;;; q-remove! q obj
  110. ;;;  Remove all occurences of obj from Q.
  111. (define (q-remove! q obj)
  112.   (set-car! q (delq! obj (car q)))
  113.   (sync-q! q))
  114.  
  115. ;;; q-push! q obj
  116. ;;;  Add obj to the front of Q
  117. (define (q-push! q obj)
  118.   (let ((h (cons obj (car q))))
  119.     (set-car! q h)
  120.     (or (cdr q) (set-cdr! q h)))
  121.   q)
  122.  
  123. ;;; enq! q obj
  124. ;;;  Add obj to the rear of Q
  125. (define (enq! q obj)
  126.   (let ((h (cons obj '())))
  127.     (if (null? (car q))
  128.     (set-car! q h)
  129.     (set-cdr! (cdr q) h))
  130.     (set-cdr! q h))
  131.   q)
  132.  
  133. ;;; q-pop! q
  134. ;;;  Take the front of Q and return it.
  135. (define (q-pop! q)
  136.   (q-empty-check q)
  137.   (let ((it (caar q))
  138.     (next (cdar q)))
  139.     (if (null? next)
  140.     (set-cdr! q #f))
  141.     (set-car! q next)
  142.     it))
  143.  
  144. ;;; deq! q
  145. ;;;  Take the front of Q and return it.
  146. (define deq! q-pop!)
  147.  
  148. ;;; q-length q
  149. ;;;  Return the number of enqueued elements.
  150. ;;;
  151. (define (q-length q) (length (car q)))
  152.  
  153. ;;; q.scm ends here
  154.